//
// Created by bleedingfight on 2020/7/7.
//
#include "threeSum.h"

std::vector<std::vector<int>> threeSum(std::vector<int> &nums) {
<<<<<<< HEAD:cxx/algorithm/src/threeSum.cc
    std::vector<std::vector<int>> result;
    int size = nums.size();
    if (size < 3)
        return result;
    std::sort(nums.begin(), nums.end());
    for (int current_index = 0; current_index < size; current_index++) {
        if (nums[current_index] > 0)
            break;
        if (current_index > 0 && nums[current_index] == nums[current_index - 1])continue;//如果当前元素和上一个元素相等，则找下一个元素
        int left_index = current_index + 1;
        int right_index = size - 1;
        while (left_index < right_index) {
            int sum_result = nums[current_index] + nums[left_index] + nums[right_index];
            if (sum_result == 0) {
                result.push_back({nums[current_index], nums[left_index], nums[right_index]});
                while (left_index < right_index && nums[left_index] == nums[left_index + 1])
                    left_index++;
                while (left_index < right_index && nums[right_index] == nums[right_index - 1])
                    right_index--;
                left_index++;
                right_index--;
            }
            if (sum_result < 0)
                left_index++;
            else if (sum_result > 0)
                right_index--;
        }
    }
    return result;
=======
  std::vector<std::vector<int>> result;
  int size = nums.size();
  if (size < 3) return result;
  std::sort(nums.begin(), nums.end());
  for (int current_index = 0; current_index < size; current_index++) {
    if (nums[current_index] > 0) break;
    if (current_index > 0 && nums[current_index] == nums[current_index - 1])
      continue;  // 如果当前元素和上一个元素相等，则找下一个元素
    int left_index = current_index + 1;
    int right_index = size - 1;
    while (left_index < right_index) {
      int sum_result =
          nums[current_index] + nums[left_index] + nums[right_index];
      if (sum_result == 0) {
        result.push_back(
            {nums[current_index], nums[left_index], nums[right_index]});
        while (left_index < right_index &&
               nums[left_index] == nums[left_index + 1])
          left_index++;
        while (left_index < right_index &&
               nums[right_index] == nums[right_index - 1])
          right_index--;
        left_index++;
        right_index--;
      }
      if (sum_result < 0)
        left_index++;
      else if (sum_result > 0)
        right_index--;
    }
  }
  return result;
>>>>>>> dev:cxx/algorithm/common/src/threeSum.cc
}
